#include <iostream>
#include <vector>
#include "lib/binary_tree.h"
using namespace std;

BinaryTreeNode* KthNode(BinaryTreeNode* root, int &k) {
  if (!root || k == 0)
    return root;

  BinaryTreeNode* target = nullptr;
  target = KthNode(root->left, k);
  if (!target) {
    if (k == 1)
      target = root;
    --k;
  }
  if (!target)
    target = KthNode(root->right, k);
  return target;
}

int main() {
  vector<int> vec = {5, 3, 7, 2, 4, 6, 8};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  int k = 3;
  auto ret = KthNode(root, k);
  cout << "The kth node in BST is: " << ret->value << endl;

  return 0;
}
